﻿using System.Diagnostics;

namespace Algorithm;

public class Kata
{
	/// <summary>
	/// 将字符串中的每个字母向后移动13位，超过最后一个字母后回到到第一个字母再继续移动，除字母外的字符不变
	/// </summary>
	/// <param name="message"></param>
	/// <returns></returns>
	public static string Rot13(string message)
	{
		var chars = message.ToArray<char>();
		for (var i = 0; i < chars.Length; i++)
		{
			if (chars[i] >= 'a' && chars[i] <= 'z')
			{
				chars[i] = (char)(chars[i] + 13);
				if (chars[i] > 'z')
				{
					chars[i] = (char)(chars[i] - 26);
				}
			}
			else if (chars[i] >= 'A' && chars[i] <= 'Z')
			{
				chars[i] = (char)(chars[i] + 13);
				if (chars[i] > 'Z')
				{
					chars[i] = (char)(chars[i] - 26);
				}
			}
		}
		return string.Join("", chars);
	}

    /// <summary>
    /// 动态规划问题: 给定一个金额和不同面值硬币，通过硬币凑出金额有几种方法
    /// </summary>
    /// <param name="money"></param>
    /// <param name="coins"></param>
    /// <returns></returns>
    public static int CountCombinations(int money, int[] coins)
    {
		int[] dp = new int[money + 1];
        List<int> list = [.. coins];
		list.Sort();
		dp[0] = 1;
        for (var i = 0; i < list.Count; i++)
		{
			for (var j = list[i]; j <= money; j++)
			{
				dp[j] += dp[j - list[i]];
			}
		}
		return dp[money];
    }
}
